package com.itheima.datastructure.priorityqueue;

import com.itheima.datastructure.queue.Queue;

/**
 * 基于<b>有序数组</b>实现-优先级队列
 *
 * @param <E> 队列中元素类型, 必须实现 Priority 接口
 */
@SuppressWarnings("all")
public class PriorityQueue2<E extends Priority> implements Queue<E> {

    Priority[] array;
    int size;

    public PriorityQueue2(int capacity) {
        array = new Priority[capacity];
    }

    @Override //O(n)
    public boolean offer(E value) {
        if (isFull()) return false;
        insert(value);
        size++;
        return true;
    }

    //插入逻辑：
    // 0 | 2 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
    //插入3
    // 0 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
    private void insert(E e) {
        int index = size - 1;
        // 从后往前找,如果找到比它优先级高的,则将这个元素后移
        while (index >= 0 && array[index].priority() > e.priority()) {
            array[index + 1] = array[index];
            index--;
        }
        // 插入
        array[index + 1] = e;
    }

    @Override //O(1)
    public E poll() {
        if (isEmpty()) return null;
        Priority priority = array[size - 1];
        size--;
        array[size] = null; // help GC
        return (E) priority;
    }

    @Override //O(1)
    public E peek() {
        if (isEmpty()) return null;
        return (E) array[size - 1];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
